package impl;

import anaydis.sort.SorterType;

import java.util.Comparator;
import java.util.List;

public class QuickSortMedOfThree extends AbstractQuickSorter {

    public QuickSortMedOfThree() {
        super(SorterType.QUICK_MED_OF_THREE);
    }

    public <T> void sort( Comparator<T> tComparator, List<T> list) {
        sort(tComparator, list, 0, list.size() - 1);
    }

    private <T> void sort(Comparator<T> tComparator, List<T> list, int left, int right) {
        if (right <= left) return;
        findMedOfThree(tComparator, list, left, right);
        int i = partition(tComparator, list, left, right);
        sort(tComparator, list, left, i - 1);
        sort(tComparator, list, i + 1, right);
    }

    private <T> void findMedOfThree(Comparator<T> tComparator, List<T> list, int left, int right) {
        int center = (left + right) / 2;

        if (greater(tComparator, list, left, center)) {
            if (!greater(tComparator, list, left, right)) {
                swap(list, left, right);
            } else if (greater(tComparator, list, center, right)) {
                swap(list, center, right);
            }
        } else if (!greater(tComparator, list, center, right)) {
            swap(list, center, right);
        } else if (greater(tComparator, list, left, right)) {
            swap(list, left, right);
        }
    }
}
